#include <vector>
#include <algorithm>

using namespace std;
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        // 思路：先排序，然后合并
        sort(intervals.begin(), intervals.end(), [](const vector<int> &intervals1, const vector<int> &intervals2)
             { return intervals1[0] < intervals2[0]; });
        vector<vector<int>> res;
        int tempStart = intervals[0][0]; // 当前合并区间的起始位置
        int tempEnd = intervals[0][1];   // 当前合并区间的结束位置
        // 遍历区间
        for (int i = 0; i < intervals.size(); ++i)
        {
            // 如果当前区间的起始位置小于等于上一个区间的结束位置，则合并
            if (tempEnd >= intervals[i][0])
            {
                tempEnd = max(tempEnd, intervals[i][1]);
            }
            else // 否则，加入结果集，并更新当前区间
            {
                res.push_back({tempStart, tempEnd});
                tempStart = intervals[i][0];
                tempEnd = intervals[i][1];
            }
        }
        // 加入最后一个区间 为什么要加上最后一个区间？因为最后一个区间可能没有被加入结果集
        // 举例来说，输入[[1,3],[2,6],[8,10],[15,18]] 最后一个区间[15,18]没有被加入结果集
        res.push_back({tempStart, tempEnd});
        return res;
    }
};